#include<vector>
#include<string>
using namespace std;
class Solution {
private:
    int getParent(vector<int>&parents, int x) {
        return parents[x] == x ? x : (parents[x] = getParent(parents, parents[x]));
    }

    void merge(vector<int>&parents, int x, int y) {
        int px = getParent(parents, x);
        int py = getParent(parents, y);
        parents[px] = py;
    }


public:
    int regionsBySlashes(vector<string>& grid) {
        if (grid.size() < 1) return 0;
        int rows = grid.size();
        int cols = grid[0].size();
        vector<int>parents(rows*cols * 4);
        for (int i = 0; i < parents.size(); ++i)
            parents[i] = i;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                int base = i * 4 * cols + j * 4;
                if (grid[i][j] == '/'|| grid[i][j] == ' ') {
                    merge(parents, base, base + 1);
                    merge(parents, base + 2, base + 3);
                }
                if(grid[i][j]=='\\' || grid[i][j] == ' '){
                    merge(parents, base + 1, base + 2);
                    merge(parents, base + 0, base + 3);
                }
                if(i!=rows-1)
                    merge(parents, base + 3, (i + 1) * 4 * cols + j * 4 + 1);
                if (j != cols - 1)
                    merge(parents, base + 2, base + 4);
            }
        }
        int res = 0;
        for (int i = 0; i < parents.size(); ++i) {
            if (parents[i] == i)
                ++res;
        }
        return res;
    }
};

int main() {
    Solution sol;
    vector<string>grid = { "  /","/  " };
    sol.regionsBySlashes(grid);
}